import random

"""
http://www.careercup.com/question?id=14859694
Given an array and a key, sum min subarray whose sum is no less than key. O(n) Time needed

Assumption: all positive intergers in the array
"""
    
def minLength(arr, k):
    min_length, sum, start = len(arr) + 1, 0, 0
    s, e = -1, -1
    for i in range(0, len(arr)):
        sum += arr[i]
        while sum - arr[start] >= k:
            sum -= arr[start]
            start += 1
        if sum >= k and i - start + 1 < min_length:
            min_length, s, e = i - start + 1, start, i
    return min_length, s, e
        
def check(arr, k):
    min_length, s, e = len(arr) + 1, -1, -1
    sum, arr_sum = 0, [0]
    for item in arr:
        sum += item
        arr_sum.append(sum)
    for i in range(0, len(arr)):
        for j in range(i + 1, len(arr)):
            if arr_sum[j] - arr_sum[i] >= k:
                if j - i < min_length:
                    min_length = j - i
                    s, e = i, j - 1
                break
    return min_length, s, e

def findMin(a, k):
    if len(a) == 0: return (-1,0,0)
    for i, v in enumerate(a):
        if v > k: return (1, i, i)
        
    minlen = -1
    minstart, minend = 0, 0
    i, j, sum = 0, 0, a[0]
    while j < len(a):
        if sum < k:
            j += 1
            if j < len(a): sum += a[j]
        else:
            while sum - a[i] >= k and i < j:
                sum -= a[i]
                i += 1
            if minlen < 0 or j - i + 1 < minlen:
                minlen = j - i + 1;
                minstart = i
                minend = j
            if j + 1 < len(a):
                sum += a[j+1]
                sum -= a[i]
            i += 1
            j += 1
        #print "tempo:" + str(minlen) + " " + str(i) + " " + str(j),
        #print "sum = " + str(sum)

    return (minlen, minstart, minend)

if __name__ == '__main__':
    for i in range(0, 20):
        from utils import *
        length = random.randint(10, 20)
        max = random.randint(10, 100)
        arr = random_arr(length, 1, max / random.randint(2, 5))
        min_length = minLength(arr, max)
        min_l2 = findMin(arr, max)
        print arr, max, min_length, check(arr, max), min_l2
